home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqbuild / solidbsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-15  |  15.5 KB  |  691 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. int leaffaces;                            /* 4 */
  5. int nodefaces;                            /* 4 */
  6. int splitnodes;                            /* 4 */
  7.  
  8. int c_solid, c_empty, c_water;                    /* 12 */
  9.  
  10. bool usemidsplit;                        /* ? */
  11.  
  12. /*============================================================================ */
  13.  
  14. /*
  15.  * ==================
  16.  * FaceSide
  17.  * 
  18.  * For BSP hueristic
  19.  * ==================
  20.  */
  21. int FaceSide(register struct visfacet *in, register struct plane *split)
  22. {
  23.   int frontcount, backcount;
  24.   vec_t dot;
  25.   int i;
  26.   vec_t *p;
  27.  
  28.   frontcount = backcount = 0;
  29.  
  30.   if (split->type < 3)
  31.     /* axial planes are fast */
  32.     for (i = 0, p = in->pts[0] + split->type; i < in->numpoints; i++, p += 3) {
  33.       if (*p > split->dist + ON_EPSILON) {
  34.     if (backcount)
  35.       return SIDE_ON;
  36.     frontcount = 1;
  37.       }
  38.       else if (*p < split->dist - ON_EPSILON) {
  39.     if (frontcount)
  40.       return SIDE_ON;
  41.     backcount = 1;
  42.       }
  43.     }
  44.   else
  45.     /* sloping planes take longer */
  46.     for (i = 0, p = in->pts[0]; i < in->numpoints; i++, p += 3) {
  47.       dot = DotProduct(p, split->normal);
  48.       dot -= split->dist;
  49.       if (dot > ON_EPSILON) {
  50.     if (backcount)
  51.       return SIDE_ON;
  52.     frontcount = 1;
  53.       }
  54.       else if (dot < -ON_EPSILON) {
  55.     if (frontcount)
  56.       return SIDE_ON;
  57.     backcount = 1;
  58.       }
  59.     }
  60.  
  61.   if (!frontcount)
  62.     return SIDE_BACK;
  63.   if (!backcount)
  64.     return SIDE_FRONT;
  65.  
  66.   return SIDE_ON;
  67. }
  68.  
  69. /*
  70.  * ==================
  71.  * ChooseMidPlaneFromList
  72.  * 
  73.  * The clipping hull BSP doesn't worry about avoiding splits
  74.  * ==================
  75.  */
  76. struct surface *ChooseMidPlaneFromList(__memBase, register struct surface *surfaces, register vec3_t mins, register vec3_t maxs)
  77. {
  78.   int j, l;
  79.   struct surface *p, *bestsurface;
  80.   vec_t bestvalue, value, dist;
  81.   struct plane *plane;
  82.  
  83.   /* pick the plane that splits the least */
  84.   bestvalue = 6 * 8192 * 8192;
  85.   bestsurface = NULL;
  86.  
  87.   for (p = surfaces; p; p = p->next) {
  88.     if (p->onnode)
  89.       continue;
  90.  
  91. #ifdef EXHAUSIVE_CHECK
  92.     if (p->planenum >= bspMem->numbrushplanes || p->planenum < 0)
  93.       Error("looking for nonexisting plane %d\n", p->planenum);
  94. #endif
  95.     plane = &bspMem->brushplanes[p->planenum];
  96.  
  97.     /* check for axis aligned surfaces */
  98.     l = plane->type;
  99.     if (l > PLANE_Z)
  100.       continue;
  101.  
  102.     /* calculate the split metric along axis l, smaller values are better */
  103.     value = 0;
  104.  
  105.     dist = plane->dist * plane->normal[l];
  106.     for (j = 0; j < 3; j++) {
  107.       if (j == l) {
  108.     value += (maxs[l] - dist) * (maxs[l] - dist);
  109.     value += (dist - mins[l]) * (dist - mins[l]);
  110.       }
  111.       else
  112.     value += 2 * (maxs[j] - mins[j]) * (maxs[j] - mins[j]);
  113.     }
  114.  
  115.     if (value > bestvalue)
  116.       continue;
  117.  
  118.     /* currently the best! */
  119.     bestvalue = value;
  120.     bestsurface = p;
  121.   }
  122.  
  123.   if (!bestsurface) {
  124.     for (p = surfaces; p; p = p->next)
  125.       if (!p->onnode)
  126.     return p;                        /* first valid surface */
  127.  
  128.     Error("ChooseMidPlaneFromList: no valid planes");
  129.   }
  130.  
  131.   return bestsurface;
  132. }
  133.  
  134. /*
  135.  * ==================
  136.  * ChoosePlaneFromList
  137.  * 
  138.  * The real BSP hueristic
  139.  * ==================
  140.  */
  141. struct surface *ChoosePlaneFromList(__memBase, register struct surface *surfaces, register vec3_t mins, register vec3_t maxs, register bool usefloors)
  142. {
  143.   int j, k, l;
  144.   struct surface *p, *p2, *bestsurface;
  145.   vec_t bestvalue, bestdistribution, value, dist;
  146.   struct plane *plane;
  147.   struct visfacet *f;
  148.  
  149.   /* pick the plane that splits the least */
  150.   bestvalue = 99999;
  151.   bestsurface = NULL;
  152.   bestdistribution = 9e30;
  153.  
  154.   for (p = surfaces; p; p = p->next) {
  155.     if (p->onnode)
  156.       continue;
  157.  
  158. #ifdef EXHAUSIVE_CHECK
  159.     if (p->planenum >= bspMem->numbrushplanes || p->planenum < 0)
  160.       Error("looking for nonexisting plane %d\n", p->planenum);
  161. #endif
  162.     plane = &bspMem->brushplanes[p->planenum];
  163.     k = 0;
  164.  
  165.     if (!usefloors && plane->normal[2] == 1)
  166.       continue;
  167.  
  168.     for (p2 = surfaces; p2; p2 = p2->next) {
  169.       if (p2 == p)
  170.     continue;
  171.       if (p2->onnode)
  172.     continue;
  173.  
  174.       for (f = p2->faces; f; f = f->next) {
  175.     if (FaceSide(f, plane) == SIDE_ON) {
  176.       k++;
  177.       if (k >= bestvalue)
  178.         break;
  179.     }
  180.  
  181.       }
  182.       if (k > bestvalue)
  183.     break;
  184.     }
  185.  
  186.     if (k > bestvalue)
  187.       continue;
  188.  
  189.     /* if equal numbers, axial planes win, then decide on spatial subdivision */
  190.     if (k < bestvalue || (k == bestvalue && plane->type < PLANE_ANYX)) {
  191.       /* check for axis aligned surfaces */
  192.       l = plane->type;
  193.  
  194.       if (l <= PLANE_Z) {                    /* axial aligned                                                 */
  195.     /* calculate the split metric along axis l */
  196.     value = 0;
  197.  
  198.     for (j = 0; j < 3; j++) {
  199.       if (j == l) {
  200.         dist = plane->dist * plane->normal[l];
  201.         value += (maxs[l] - dist) * (maxs[l] - dist);
  202.         value += (dist - mins[l]) * (dist - mins[l]);
  203.       }
  204.       else
  205.         value += 2 * (maxs[j] - mins[j]) * (maxs[j] - mins[j]);
  206.     }
  207.  
  208.     if (value > bestdistribution && k == bestvalue)
  209.       continue;
  210.     bestdistribution = value;
  211.       }
  212.       /* currently the best! */
  213.       bestvalue = k;
  214.       bestsurface = p;
  215.     }
  216.  
  217.   }
  218.  
  219.   return bestsurface;
  220. }
  221.  
  222. /*
  223.  * ==================
  224.  * SelectPartition
  225.  * 
  226.  * Selects a surface from a linked list of surfaces to split the group on
  227.  * returns NULL if the surface list can not be divided any more (a leaf)
  228.  * ==================
  229.  */
  230. struct surface *SelectPartition(__memBase, register struct surface *surfaces)
  231. {
  232.   int i;
  233.   short int j;
  234.   vec3_t mins, maxs;
  235.   struct surface *p, *bestsurface;
  236.  
  237.   /* count onnode surfaces */
  238.   i = 0;
  239.   bestsurface = NULL;
  240.   for (p = surfaces; p; p = p->next)
  241.     if (!p->onnode) {
  242.       i++;
  243.       bestsurface = p;
  244.     }
  245.  
  246.   if (i == 0)
  247.     return NULL;
  248.  
  249.   if (i == 1)
  250.     return bestsurface;                        /* this is a final split */
  251.  
  252.   /* calculate a bounding box of the entire surfaceset */
  253.   for (i = 0; i < 3; i++) {
  254.     mins[i] = 99999;
  255.     maxs[i] = -99999;
  256.   }
  257.  
  258.   for (p = surfaces; p; p = p->next)
  259.     for (j = 0; j < 3; j++) {
  260.       if (p->mins[j] < mins[j])
  261.     mins[j] = p->mins[j];
  262.       if (p->maxs[j] > maxs[j])
  263.     maxs[j] = p->maxs[j];
  264.     }
  265.  
  266.   if (usemidsplit)                        /* do fast way for clipping hull */
  267.     return ChooseMidPlaneFromList(bspMem, surfaces, mins, maxs);
  268.  
  269.   /* do slow way to save poly splits for drawing hull */
  270. #if 0
  271.   bestsurface = ChoosePlaneFromList(surfaces, mins, maxs, FALSE);
  272.   if (bestsurface)
  273.     return bestsurface;
  274. #endif
  275.   return ChoosePlaneFromList(bspMem, surfaces, mins, maxs, TRUE);
  276. }
  277.  
  278. /*============================================================================ */
  279.  
  280. /*
  281.  * =================
  282.  * CalcSurfaceInfo
  283.  * 
  284.  * Calculates the bounding box
  285.  * =================
  286.  */
  287. void CalcSurfaceInfo(register struct surface *surf)
  288. {
  289.   int i;
  290.   short int j;
  291.   struct visfacet *f;
  292.  
  293.   if (!surf->faces)
  294.     Error("CalcSurfaceInfo: surface without a face");
  295.  
  296.   /* calculate a bounding box */
  297.   for (i = 0; i < 3; i++) {
  298.     surf->mins[i] = 99999;
  299.     surf->maxs[i] = -99999;
  300.   }
  301.  
  302.   for (f = surf->faces; f; f = f->next) {
  303.     if (f->contents[0] >= 0 || f->contents[1] >= 0)
  304.       Error("Bad contents");
  305.     for (i = 0; i < f->numpoints; i++)
  306.       for (j = 0; j < 3; j++) {
  307.     if (f->pts[i][j] < surf->mins[j])
  308.       surf->mins[j] = f->pts[i][j];
  309.     if (f->pts[i][j] > surf->maxs[j])
  310.       surf->maxs[j] = f->pts[i][j];
  311.       }
  312.   }
  313. }
  314.  
  315. /*
  316.  * ==================
  317.  * DividePlane
  318.  * ==================
  319.  */
  320. void DividePlane(__memBase, register struct surface *in, register struct plane *split, register struct surface **front, register struct surface **back)
  321. {
  322.   struct visfacet *facet, *next;
  323.   struct visfacet *frontlist, *backlist;
  324.   struct visfacet *frontfrag, *backfrag;
  325.   struct surface *news;
  326.   struct plane *inplane;
  327.  
  328. #ifdef EXHAUSIVE_CHECK
  329.   if (inplane->planenum >= bspMem->numbrushplanes || inplane->planenum < 0)
  330.     Error("looking for nonexisting plane %d\n", inplane->planenum);
  331. #endif
  332.   inplane = &bspMem->brushplanes[in->planenum];
  333.  
  334.   /* parallel case is easy */
  335.   if (VectorCompare(inplane->normal, split->normal)) {
  336.     /* check for exactly on node */
  337.     if (inplane->dist == split->dist) {                /* divide the facets to the front and back sides */
  338.  
  339.       news = AllocSurface();
  340.       *news = *in;
  341.  
  342.       facet = in->faces;
  343.       in->faces = NULL;
  344.       news->faces = NULL;
  345.       in->onnode = news->onnode = TRUE;
  346.  
  347.       for (; facet; facet = next) {
  348.     next = facet->next;
  349.     if (facet->planeside == 1) {
  350.       facet->next = news->faces;
  351.       news->faces = facet;
  352.     }
  353.     else {
  354.       facet->next = in->faces;
  355.       in->faces = facet;
  356.     }
  357.       }
  358.  
  359.       if (in->faces)
  360.     *front = in;
  361.       else
  362.     *front = NULL;
  363.       if (news->faces)
  364.     *back = news;
  365.       else
  366.     *back = NULL;
  367.       return;
  368.     }
  369.  
  370.     if (inplane->dist > split->dist) {
  371.       *front = in;
  372.       *back = NULL;
  373.     }
  374.     else {
  375.       *front = NULL;
  376.       *back = in;
  377.     }
  378.     return;
  379.   }
  380.  
  381.   /*
  382.    * do a real split.  may still end up entirely on one side
  383.    * OPTIMIZE: use bounding box for fast test
  384.    */
  385.   frontlist = NULL;
  386.   backlist = NULL;
  387.  
  388.   for (facet = in->faces; facet; facet = next) {
  389.     next = facet->next;
  390.     SplitFace(facet, split, &frontfrag, &backfrag);
  391.     if (frontfrag) {
  392.       frontfrag->next = frontlist;
  393.       frontlist = frontfrag;
  394.     }
  395.     if (backfrag) {
  396.       backfrag->next = backlist;
  397.       backlist = backfrag;
  398.     }
  399.   }
  400.  
  401.   /* if nothing actually got split, just move the in plane */
  402.   if (frontlist == NULL) {
  403.     *front = NULL;
  404.     *back = in;
  405.     in->faces = backlist;
  406.     return;
  407.   }
  408.  
  409.   if (backlist == NULL) {
  410.     *front = in;
  411.     *back = NULL;
  412.     in->faces = frontlist;
  413.     return;
  414.   }
  415.  
  416.   /* stuff got split, so allocate one new plane and reuse in */
  417.   news = AllocSurface();
  418.   *news = *in;
  419.   news->faces = backlist;
  420.   *back = news;
  421.  
  422.   in->faces = frontlist;
  423.   *front = in;
  424.  
  425.   /* recalc bboxes and flags */
  426.   CalcSurfaceInfo(news);
  427.   CalcSurfaceInfo(in);
  428. }
  429.  
  430. /*
  431.  * ==================
  432.  * DivideNodeBounds
  433.  * ==================
  434.  */
  435. void DivideNodeBounds(register struct node *node, register struct plane *split)
  436. {
  437.   VectorCopy(node->mins, node->children[0]->mins);
  438.   VectorCopy(node->mins, node->children[1]->mins);
  439.   VectorCopy(node->maxs, node->children[0]->maxs);
  440.   VectorCopy(node->maxs, node->children[1]->maxs);
  441.  
  442.   /* OPTIMIZE: sloping cuts can give a better bbox than this... */
  443.   if (split->type > 2)
  444.     return;
  445.  
  446.   node->children[0]->mins[split->type] =
  447.     node->children[1]->maxs[split->type] = split->dist;
  448. }
  449.  
  450. /*
  451.  * ==================
  452.  * LinkConvexFaces
  453.  * 
  454.  * Determines the contents of the leaf and creates the final list of
  455.  * original faces that have some fragment inside this leaf
  456.  * ==================
  457.  */
  458. void LinkConvexFaces(register struct surface *planelist, register struct node *leafnode)
  459. {
  460.   struct visfacet *f, *next;
  461.   struct surface *surf, *pnext;
  462.   int i, count;
  463.  
  464.   leafnode->faces = NULL;
  465.   leafnode->contents = 0;
  466.   leafnode->planenum = -1;
  467.  
  468.   count = 0;
  469.   for (surf = planelist; surf; surf = surf->next) {
  470.     for (f = surf->faces; f; f = f->next) {
  471.       count++;
  472.       if (!leafnode->contents)
  473.     leafnode->contents = f->contents[0];
  474.       else if (leafnode->contents != f->contents[0])
  475.     Error("Mixed face contents in leafnode");
  476.     }
  477.   }
  478.  
  479.   if (!leafnode->contents)
  480.     leafnode->contents = CONTENTS_SOLID;
  481.  
  482.   switch (leafnode->contents) {
  483.     case CONTENTS_EMPTY:
  484.       c_empty++;
  485.       break;
  486.     case CONTENTS_SOLID:
  487.       c_solid++;
  488.       break;
  489.     case CONTENTS_WATER:
  490.     case CONTENTS_SLIME:
  491.     case CONTENTS_LAVA:
  492.     case CONTENTS_SKY:
  493.       c_water++;
  494.       break;
  495.     default:
  496.       Error("LinkConvexFaces: bad contents number");
  497.   }
  498.  
  499.   /* write the list of faces, and free the originals */
  500.   leaffaces += count;
  501.   if (!(leafnode->markfaces = (struct visfacet **)tmalloc(sizeof(struct visfacet *) * (count + 1))))
  502.       Error(failed_memoryunsize, "markfaces");
  503.  
  504.   i = 0;
  505.   for (surf = planelist; surf; surf = pnext) {
  506.     pnext = surf->next;
  507.     for (f = surf->faces; f; f = next) {
  508.       next = f->next;
  509.       leafnode->markfaces[i] = f->original;
  510.       i++;
  511.       FreeFace(f);
  512.     }
  513.     FreeSurface(surf);
  514.   }
  515.   leafnode->markfaces[i] = NULL;                /* sentinal */
  516.  
  517. }
  518.  
  519. /*
  520.  * ==================
  521.  * LinkNodeFaces
  522.  * 
  523.  * Returns a duplicated list of all faces on surface
  524.  * ==================
  525.  */
  526. struct visfacet *LinkNodeFaces(__memBase, register struct surface *surface)
  527. {
  528.   struct visfacet *f, *new, **prevptr;
  529.   struct visfacet *list;
  530.  
  531.   list = NULL;
  532.  
  533.   /* subdivide */
  534.   prevptr = &surface->faces;
  535.   while (1) {
  536.     f = *prevptr;
  537.     if (!f)
  538.       break;
  539.     SubdivideFace(bspMem, f, prevptr);
  540.     f = *prevptr;
  541.     prevptr = &f->next;
  542.   }
  543.  
  544.   /* copy */
  545.   for (f = surface->faces; f; f = f->next) {
  546.     nodefaces++;
  547.     new = AllocFace(f->numpoints);
  548.     CopyFace(new, f);
  549.     f->original = new;
  550.     new->next = list;
  551.     list = new;
  552.   }
  553.  
  554.   return list;
  555. }
  556.  
  557. /*
  558.  * ==================
  559.  * PartitionSurfaces
  560.  * ==================
  561.  */
  562. void PartitionSurfaces(__memBase, register struct surface *surfaces, register struct node *node)
  563. {
  564.   struct surface *split, *p, *next;
  565.   struct surface *frontlist, *backlist;
  566.   struct surface *frontfrag, *backfrag;
  567.   struct plane *splitplane;
  568.  
  569.   split = SelectPartition(bspMem, surfaces);
  570.   if (!split) {                            /* this is a leaf node */
  571.  
  572.     node->planenum = PLANENUM_LEAF;
  573.     LinkConvexFaces(surfaces, node);
  574.     return;
  575.   }
  576.  
  577.   splitnodes++;
  578.   node->faces = LinkNodeFaces(bspMem, split);
  579.   node->children[0] = AllocNode();
  580.   node->children[1] = AllocNode();
  581.   node->planenum = split->planenum;
  582.  
  583. #ifdef EXHAUSIVE_CHECK
  584.   if (split->planenum >= bspMem->numbrushplanes || split->planenum < 0)
  585.     Error("looking for nonexisting plane %d\n", split->planenum);
  586. #endif
  587.   splitplane = &bspMem->brushplanes[split->planenum];
  588.  
  589.   DivideNodeBounds(node, splitplane);
  590.  
  591.   /* multiple surfaces, so split all the polysurfaces into front and back lists */
  592.   frontlist = NULL;
  593.   backlist = NULL;
  594.  
  595.   for (p = surfaces; p; p = next) {
  596.     next = p->next;
  597.     DividePlane(bspMem, p, splitplane, &frontfrag, &backfrag);
  598.     if (frontfrag && backfrag) {
  599.       /*
  600.        * the plane was split, which may expose oportunities to merge
  601.        * adjacent faces into a single face
  602.        *                      MergePlaneFaces (frontfrag);
  603.        *                      MergePlaneFaces (backfrag);
  604.        */
  605.     }
  606.  
  607.     if (frontfrag) {
  608.       if (!frontfrag->faces)
  609.     Error("surface with no faces");
  610.       frontfrag->next = frontlist;
  611.       frontlist = frontfrag;
  612.     }
  613.     if (backfrag) {
  614.       if (!backfrag->faces)
  615.     Error("surface with no faces");
  616.       backfrag->next = backlist;
  617.       backlist = backfrag;
  618.     }
  619.   }
  620.  
  621.   PartitionSurfaces(bspMem, frontlist, node->children[0]);
  622.   PartitionSurfaces(bspMem, backlist, node->children[1]);
  623. }
  624.  
  625. /*
  626.  * ==================
  627.  * DrawSurface
  628.  * ==================
  629.  */
  630. void DrawSurface(register struct surface *surf)
  631. {
  632.   struct visfacet *f;
  633.  
  634.   for (f = surf->faces; f; f = f->next)
  635.     Draw_DrawFace(f);
  636. }
  637.  
  638. /*
  639.  * ==================
  640.  * DrawSurfaceList
  641.  * ==================
  642.  */
  643. void DrawSurfaceList(register struct surface *surf)
  644. {
  645.   Draw_ClearWindow();
  646.   while (surf) {
  647.     DrawSurface(surf);
  648.     surf = surf->next;
  649.   }
  650. }
  651.  
  652. /*
  653.  * ==================
  654.  * SolidBSP
  655.  * ==================
  656.  */
  657. struct node *SolidBSP(__memBase, struct surface *surfhead, bool midsplit)
  658. {
  659.   short int i;
  660.   struct node *headnode;
  661.  
  662.   mprintf("----- SolidBSP ----------\n");
  663.  
  664.   headnode = AllocNode();
  665.   usemidsplit = midsplit;
  666.  
  667.   /* calculate a bounding box for the entire model */
  668.   for (i = 0; i < 3; i++) {
  669.     headnode->mins[i] = brushset->mins[i] - SIDESPACE;
  670.     headnode->maxs[i] = brushset->maxs[i] + SIDESPACE;
  671.   }
  672.  
  673.   /* recursively partition everything */
  674.   Draw_ClearWindow();
  675.   splitnodes = 0;
  676.   leaffaces = 0;
  677.   nodefaces = 0;
  678.   c_solid = c_empty = c_water = 0;
  679.  
  680.   PartitionSurfaces(bspMem, surfhead, headnode);
  681.  
  682.   mprintf("%5i split nodes\n", splitnodes);
  683.   mprintf("%5i solid leafs\n", c_solid);
  684.   mprintf("%5i empty leafs\n", c_empty);
  685.   mprintf("%5i water leafs\n", c_water);
  686.   mprintf("%5i leaffaces\n", leaffaces);
  687.   mprintf("%5i nodefaces\n", nodefaces);
  688.  
  689.   return headnode;
  690. }
  691.